package sort;

/**
 * @description: 快速排序(nlgn) 不稳定 最好数组数据是随机的
 * @title: QuickSort
 * @author: zp
 * @date: 2021/11/17 20:26
 */
public class QuickSort extends BaseSort{
    public static void main(String[] args) {
        int count=10000000;
        Integer[] ints=new Integer[count];
        for (int i = 0; i <count ; i++) {
            ints[i]=(int) (Math.random()*count);
        }
        long start=System.currentTimeMillis();
        sort(ints);
        long end=System.currentTimeMillis();
        System.out.println((end-start));
        //show(ints);
    }

    public static void sort(Comparable[] a){
        sort(a, 0, a.length - 1);
    }
    /**
     * @description:递归寻找基准点 按基准点分割大小左右
     * @author: zp
     * @date: 2021/11/17 21:09
     * @param: a
     * @param: lo
     * @param: hi
     * @return: void
     */
    private static void sort(Comparable[] a,int lo,int hi){
        if(hi<=lo){
            return;
        }
        //找到下一次排序的基准点
        int j = partition(a, lo, hi);
        //基准点之前的数据
        sort(a, lo, j-1);
        //基准点之后的数据
        sort(a, j+1, hi);
    }

    private static int partition(Comparable[] a, int lo, int hi) {
        int i = lo;
        int j = hi + 1;
        //分割后数组的第一位元素为分割点
        Comparable v = a[lo];
        while (true){
            //在基准点左边找到大于基准点的位置 保留i
            while (less(a[++i],v)){
                if(i==hi){
                    break;
                }
            }
            //在基准点右边找到小于基准点的位置 保留j
            while (less(v,a[--j])){
                if(j==lo){
                    break;
                }
            }
            //当i和j未在一起或者左边已经遍历超过基准点的时候退出循环
                if(i>=j){
                break;
            }
            //找到基准点左边和右边不合理大小的数 交换两个数的位置
            exch(a,i,j);

        }
        //当这个基准点的左边都是小于基准点的数据 右边都是大于基准点的数据 把基准点切割的数组的第一个和未交换的最后一个位置互换 产生新的基准点 返回j的位置
        exch(a,lo,j);

        return j;
    }
}
